class Solution:
    def lastStoneWeightII(self, stones: List[int]) -> int:
        # 计算石头总重量
        sum = 0
        for i in stones:
            sum += i
        # 计算目标重量，即石头总重量的一半
        target = sum // 2
        # 创建一个长度为target+1的dp数组，用于记录每个重量是否可以达到
        dp = [0] * (target + 1)
        # 遍历石头数组
        for i in range(len(stones)):
            # 从target开始，倒序遍历，避免重复计算
            for j in range(target, stones[i] - 1, -1):
                # 更新dp数组，记录当前重量是否可以达到
                dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])
        # 返回最后一块石头的重量，即总重量减去dp数组中最后一个元素的两倍
        return sum - 2 * dp[-1]